package simple;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
 *
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 * */
public class PascalsTriangleII {

    /**
     * 空间复杂度为O(rowIndex)
     * 对于元素list[1][1] 其等于 list[0][0] + list[0][1]
     * 故对于下一行的计算 依赖于当前行的前面元素。
     * 而前面元素计算出来后就会被覆盖，这时候我们就可以考虑倒着去算，就不会覆盖到前面的了。
     * */
    class Solution {
        public List<Integer> getRow(int rowIndex) {
            List<Integer> res = new ArrayList<>();
            res.add(1);
            for (int i = 1; i <= rowIndex; i++) {
                res.add(0);
                for (int j = i; j > 0; j--){
                    res.set(j, res.get(j-1) + res.get(j));
                }
            }
            return res;
        }
    }
}
